package a10_动态规划;

/**
 * <p>
 * a09_不同的二叉搜索树复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/10
 */
public class a09_不同的二叉搜索树复习1 {
    //dp[i]:i个节点的二叉树有dp[i]种情况
    //dp[3]:
    //以1为头节点：左边0个节点有多少种情况，右边2个节点有多少种情况
    //以2为头节点：左边1个节点有多少种情况，右边1个节点有多少种情况
    //以3为头节点：左边2个节点有多少种情况，右边0个节点有多少种情况
    //dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

    //初始化：dp[0]=1 dp[1]=1 dp[2]=2
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = dp[i] + dp[j-1] * dp[i-j];
            }
        }

        return dp[n];
    }
}
